package com.sjf.day02.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author <huangtang>
 * @since 2021/12/27 16:25
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-45,78,0,23,-567,70,5,467};
        //int[] arr = new int[100000];
        //for (int i = 0; i < 100000; i++) {
        //    arr[i] = (int)(Math.random() * 1000000); //生产 0 - 100000的随机数
        //}
        //long t1 = System.currentTimeMillis();
        quickSort2(arr,0,arr.length-1);
        //System.out.println("用时："+(System.currentTimeMillis()-t1)); //19ms
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort2(int[] arr,int left,int right){
        if(left < right){
            int index = getIndex2(arr,left,right); //寻找基准数得索引
            //进行迭代对index之前和之后数组进行相同得操作使基准数的前后数组都有序
            quickSort2(arr,left,index-1);
            quickSort2(arr,index+1,right);
        }
    }

    /**
     * 获取基准数的索引，用于下一次迭代
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int getIndex(int[] arr,int left,int right){
        int tmp = arr[left];//暂存基准数据
        while(left<right){
            //当尾部的元素大于等于基准数时，尾部指针前移
            while(left < right && arr[right] >= tmp){
                right--;
            }
            //如果队尾元素小于tmp了，将其赋值给left
            arr[left] = arr[right];

            //当队首元小于等于基准数时，头部指针后移
            while(left < right && arr[left] <= tmp){
                left++;
            }
            //如果队首元素大于基准数时，将其赋给right
            arr[right] = arr[left];
        }
        //跳出循环时left和right相等，此时的left和right就是基准的索引位置
        arr[left] = tmp;
        return left;
    }

    public static int getIndex2(int[] arr,int left,int right){
        int temp = arr[left]; //暂存基准数
        while(left<right){
            //当尾部的元素大于等于基准数时，尾部指针前移
            while(arr[right] >= temp && left < right){
                right--;
            }
            //当尾部元素小于基准数时，将其赋值给left
            arr[left] = arr[right];

            while(left < right && arr[left] <= temp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }

    /**
     * 快速排序 方法一 -》 每次以中轴值作为基准
     * @param arr
     */
    public static void quickSort(int[] arr,int left,int right){
        int l = left; //左下标
        int r = right;//右下标
        int pivot = arr[(left+right)/2];//中轴值

        while(l < r) { //比pivot小的值放左边，大的放右边
            while(arr[l]<pivot) { //在pivot左边一直找，找到比pivot大的值就停止
                l += 1;
            }
            while(arr[r]>pivot){ //在pivot右边一直找，找到比pivot小的值就停止
                r -= 1;
            }
            if(l >= r){ //l==r时，左边全是小于pivot的，右边全是大于pivot
                break;
            }

            //交换
            swap(arr,l,r);
            //如果交换完后，发现arr[l]==pivot
            if(arr[l] == pivot){
                r--; //防止再次比较
            }
            //如果交换完后，发现arr[r]==pivot
            if(arr[r] == pivot){
                l++; //防止再次比较
            }
        }
            if(l == r){ //防止后面递归时栈溢出
                l+=1;
                r-=1;
            }
            //向左递归
            if(left<r){
                quickSort(arr,left,r);
            }
            //向右递归
            if(right>l){
                quickSort(arr,l,right);
            }
    }


    public static void swap(int[] a, int i, int j) {
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[i] ^ a[j];
    }
}
